 \documentclass [10pt]{article}

  
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{epsfig} 
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{xspace}
\usepackage{todonotes}
\usepackage{listings}

\newcommand{\true}{true}
\newcommand{\false}{false}


   \pagestyle{plain}
   \bibliographystyle{plain}


\title{Formale Methoden der Informatik \\
 Block 1: Computability and Complexity }
\author{Exercises}

\date{ST 2023}

\author{\textbf{name (matriculation number)}}

  \newtheorem{theorem}{Theorem}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{conjecture}[theorem]{Conjecture}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{remark}[theorem]{Remark}
  \newtheorem{exercise}[theorem]{Exercise}

  \newcommand{\ra}{\rightarrow}
  \newcommand{\Ra}{\Rightarrow}
  \newcommand{\La}{\Leftarrow}
  \newcommand{\la}{\leftarrow}
  \newcommand{\LR}{\Leftrightarrow}

  \renewcommand{\phi}{\varphi}
  \renewcommand{\theta}{\vartheta}


\newcommand{\ccfont}[1]{\protect\mathsf{#1}}
\newcommand{\NP}{\ccfont{NP}}

\newcommand{\NN}{\textbf{N}}
\newcommand{\IN}{\textbf{Z}}
\newcommand{\bigO}{\mathrm{O}}
\newcommand{\bigOmega}{\Omega}
\newcommand{\bigTheta}{\Theta}
\newcommand{\REACHABILITY}{\mbox{\bf REACHABILITY}}
\newcommand{\MAXFLOW}{\mbox{\bf MAX FLOW}}
\newcommand{\MAXFLOWD}{\mbox{\bf MAX FLOW(D)}}
\newcommand{\MAXFLOWSUB}{\mbox{\bf MAX FLOW SUBOPTIMAL}}
\newcommand{\MATCHING}{\mbox{\bf BIPARTITE MATCHING}}
\newcommand{\TSP}{\mbox{\bf TSP}}
\newcommand{\TSPD}{\mbox{\bf TSP(D)}}

\newcommand{\TwoSAT}{\mbox{\bf 2-SAT}\xspace}
\newcommand{\ThreeCol}{\mbox{\bf 3-COLORABILITY}}
\newcommand{\TwoCol}{\mbox{\bf 2-COLORABILITY}}
\newcommand{\OneCol}{\mbox{\bf 1-COLORABILITY}}
\newcommand{\kCol}{\mbox{\bf k-COLORABILITY}}
\newcommand{\HamPath}{\mbox{\bf HAMILTON-PATH}}
\newcommand{\HamCycle}{\mbox{\bf HAMILTON-CYCLE}}

\newcommand{\ONESAT}{\mbox{\bf 1-IN-3-SAT}}
\newcommand{\MONONESAT}{\mbox{\bf MONOTONE 1-IN-3-SAT}}
\newcommand{\kSAT}{\mbox{\bf k-SAT}}
\newcommand{\NAESAT}{\mbox{\bf NAESAT}}


\renewcommand{\labelenumi}{(\alph{enumi})}

%%% useful macros for Turing machines:
\newcommand{\blank}{\sqcup}
\newcommand{\ssym}{\triangleright}
\newcommand{\esym}{\triangleleft}
\newcommand{\halt}{\mbox{h}}
\newcommand{\yess}{\mbox{``yes''}}
\newcommand{\nos}{\mbox{``no''}}
\newcommand{\lmove}{\leftarrow}
\newcommand{\rmove}{\rightarrow}
\newcommand{\stay}{-}
\newcommand{\diverge}{\nearrow}
\newcommand{\yields}[1]{\stackrel{#1}{\rightarrow}}

\newcommand{\HALTING}{\mbox{\bf HALTING}}

\newcommand{\SetCov}{\mbox{\bf Set Cover}\xspace}

\newcommand{\com}[1]{\todo[inline,color=red!70!orange!30!white]{COMMENT: #1}}



\begin{document}


\maketitle
\textbf{The deadline for submitting your solutions for review is
  April 16, 2023. Please use the \LaTeX-template of this sheet for your submission.
  } 



\begin{exercise}
  By providing a many-one reduction from the \textbf{HALTING} problem to
  \textbf{REACHABLE-CODE}, prove that \textbf{REACHABLE-CODE} is
  undecidable.
\end{exercise}

\medskip

\noindent
\textbf{Solution:}

\textbf{HALTING} instance: program $\Pi_H$, input string $I_H$

\textbf{REACHABLE-CODE} instance: program $\Pi_{RC}$, line number $n$

To reduce an instance of \textbf{HALTING} $(\Pi_H, I_H)$ to an instance of \textbf{REACHABLE-CODE} $(\Pi_{RC}, n)$, we can define a program $\Pi$ as follows:

\begin{lstlisting}[mathescape=true]
Boolean $\Pi$(String $\Pi_H$, String $I_H$)
    $\Pi_H$($I_H$)
    return true
\end{lstlisting}

$\Pi$ has a line $L$ on which it returns if it terminates, that is to say, it reaches that line if it terminates. We simply set $n$ to be this line $L$ and $\Pi_{RC}$ to be $\Pi$, $(\Pi_H, I_H) \mapsto (\Pi, L)$.

$\Rightarrow$: assume $\Pi_H$ halts on instance $I_H$, then $\Pi$ returns true after line $L$ was reached, because $L$ was the line on which $\Pi_H$ terminates. Thus, there exists an input for $\Pi_{RC}$ such that line $n$ is reached.

$\Leftarrow$: assume line $L$ was reached, $\Pi_H$ must have terminated and thus $\Pi$ returns \texttt{true}.

\medskip

\begin{exercise}
    By providing a semi-decision procedure, prove that \textbf{CORRECTNESS} is
    semi-decidable.
\end{exercise}

\medskip

\noindent
\textbf{Solution:}

\textbf{CORRECTNESS} instance: program $\Pi$ of type (String, String) $\rightarrow$ String, strings $I_1$, $I_2$

We define a program $\Pi_C$ that serves as a decision procedure.

\begin{lstlisting}[mathescape=true]
Boolean $\Pi_C$($\Pi$, $I_1$, $I_2$)
    return $\Pi(I_1) = I_2$
\end{lstlisting}

If $\Pi_C$ terminates, it decides program correctness.

Going the other way, if $(\Pi, I_1, I_2)$ is a yes instance, then $\Pi$ must have returned $I_2$ on input $I_1$ and thus $\Pi_C$ terminates, returning \texttt{true}.
If $(\Pi, I_1, I_2)$ is a no instance, then $\Pi$ might return $I_2$ on input $I_1$, with $\Pi_C$ only returning \texttt{false} in case $\Pi$ terminates.
It follows that \textbf{CORRECTNESS} is semi-decidable.

\medskip

\begin{exercise}
    By providing a many-one reduction from \textbf{CORRECTNESS} to \textbf{HALTING},
    prove that \textbf{CORRECTNESS} is semi-decidable.
\end{exercise}

\medskip

\noindent
\textbf{Solution:}

\textbf{CORRECTNESS} instance: program $\Pi$ of type (String, String) $\rightarrow$ String, strings $I_1$, $I_2$

\textbf{HALTING} instance: program $\Pi_H$, string $I_H$

We reduce an instance of \textbf{CORRECTNESS} $(\Pi, I_1, I_2)$ by using an intermediary decision procedure $\Pi_C$, $(\Pi, I_1, I_2) \mapsto (\Pi_C, I_1)$.

\begin{lstlisting}[mathescape=true]
Boolean $\Pi_C$(String $\Pi$, String $I_1$, String $I_2$)
    if $\Pi$($I_1$) $!=$ $I_2$:
        while true do {}
    return true
\end{lstlisting}

$\Rightarrow$: assume $\Pi(I_1) = I_2$, then $\Pi$ is correct and halts, $\Pi_C$ returns \texttt{true}.

$\Leftarrow$: assume $\Pi_C$ halts on input $I_1$, then $\Pi$ must have returned $I_2$ on input $I_1$.
If that weren't the case, $\Pi_C$ would have entered the infinite loop and never returned \texttt{true}.

Because \textbf{HALTING} is semi-decidable, we know that \textbf{CORRECTNESS} is also semi-decidable.
But it also follows from the reduction.
If $\Pi_C$ terminates, then $\Pi$ must have also terminated and as can be seen above $\Pi$ must have returned the correct answer.
In case $\Pi_C$ does not terminate, $\Pi$ must have been incorrect or not have terminated by itself.

\medskip

\begin{exercise}
    Prove that the following problem is undecidable:

  \begin{center}
    \fbox{
      \begin{minipage}[c]{.9\linewidth}
        \textbf{ALL-FALSE}

\medskip INSTANCE: A program $\Pi$ that takes as input a natural number and
returns \emph{true} or \emph{false}. It is guaranteed that $\Pi$ terminates on
any input.
 

\medskip

QUESTION: Is it the case that  $\Pi(k)=false$ for \emph{all} natural numbers $k$?
      \end{minipage}
    }
  \end{center}

  Hint: Reduce from the \textbf{co-HALTING} problem.
  For your proof you may assume the availability of an interpreter 
  %instances of \textbf{HALTING}. In particular, you have available a decision
  %procedure 
	$\Pi_{int}$ that does the following:
  \begin{enumerate}\item $\Pi_{int}$ takes as input a program $\Pi$,  a
    string $I$, and a natural number $n$.

  \item $\Pi_{int}$ emulates the first $n$ steps of the run of $\Pi$ on
    $I$. If $\Pi$ terminates on $I$ within $n$ steps, then $\Pi_{int}$ returns
    \emph{true}. Otherwise, $\Pi_{int}$ returns \emph{false}.
  \end{enumerate}

    
\end{exercise}

\medskip

\noindent
\textbf{Solution:}

\textbf{co-HALTING} instance: program $\Pi_H$, string $I_H$

\textbf{ALL-FALSE} instance: program $\Pi$ of type (Integer) $\rightarrow$ Boolean, $\Pi$ always terminates

In order to reduce instances of \textbf{co-HALTING} to instances of \textbf{ALL-FALSE}, the following mapping needs to be achieved:

$\Pi_H(I_H)\ does\ not\ halt \mapsto \forall k \in \mathbb{N} : \Pi(k) = \texttt{false}$

$\Pi_H(I_H)\ halts \mapsto \neg \forall k \in \mathbb{N} : \Pi(k) = \texttt{false} = \exists k \in \mathbb{N} : \Pi(k) = \texttt{true}$

\begin{lstlisting}[mathescape=true]
Boolean $\Pi_A$($\Pi_H$, $I_H$, $k$)
    return $\Pi_{int}(\Pi_H, I_H, k)$
\end{lstlisting}

$\Rightarrow$: assume $\Pi_H$ halts on $I_H$ (no instance of \textbf{co-HALTING}), then there must exist an integer $k$ for which $\Pi_{int}$ returns \texttt{true}.
In that case, there is a $k$ for which $\Pi_A$ returns true and we have a no instance of \textbf{ALL-FALSE}.

$\Leftarrow$: assume there exists an integer $k$ for which $\Pi_A$ returns \texttt{true}, then $\Pi_{int}$ must have returned true and thus, $\Pi_H$ must have halted on input $I_H$ at line $k$ (no instance of \textbf{co-HALTING}).

This reduction shows us that \textbf{ALL-FALSE} is at least as hard as \textbf{co-HALTING}, which we know to be undecidable.

\medskip

\begin{exercise}
  	Consider the following decision problem:

\medskip     
   
    \fbox{
      \begin{minipage}[c]{.9\linewidth}
	      \textbf{REMOVE-CLAUSE 3SAT (RC3SAT)} 
	\smallskip

	      INSTANCE:  A 3-CNF formula 
	      $\varphi=\bigwedge_{i=1}^m (l_{i1}\vee l_{i2} \vee l_{i3})$.
\medskip

QUESTION: 
 Does there exist a clause $c$ in $\varphi$ such that removal of $c$ from $\varphi$ yields a satisfiable formula.\\
	Formally: does there exist $j$ ($1\leq j\leq m$) such that 
	      $\varphi=
	      	\bigwedge_{i=1}^{j-1} (l_{i1}\vee l_{i2} \vee l_{i3})\wedge
	      	\bigwedge_{i=j+1}^{m} (l_{i1}\vee l_{i2} \vee l_{i3})$ is satisfiable.

      \end{minipage}
    }


\medskip
	\begin{enumerate}
		\item 
 Give a formal proof that \textbf{RC3SAT} is in NP, i.e.\ define a
  certificate relation and discuss that it is polynomially balanced and
  polynomial-time decidable.
		\item 
Show NP-hardness of \textbf{RC3SAT} by a many-one reduction from
\textbf{3-SAT}.
	\end{enumerate}


\end{exercise}

\medskip

\noindent
\textbf{Solution:}

We provide the relation $R = (\varphi, (j, \mu))$.
It is polynomially balanced, because j is just a single number and $\mu$ is polynomial in the number of atoms (it is at most $3m$, which is the number of atoms).
It is also polynomially decidable, because just like with SAT, a PTIME algorithms can iterate all clauses (and skip the j-th one) to check whether $\varphi$ is satisfied under $\mu$.

\textbf{3-SAT} instance: $\varphi_3$

\textbf{RC3SAT} instance: $\varphi_R$

We reduce from the original formula by introducing an additional independent literal and two clauses: $(\varphi_3) \mapsto (\varphi_R)$, $\varphi_R = \varphi_3 \land (l \lor l \lor l) \land (\neg l \lor \neg l \lor \neg l)$

$\Rightarrow$: assume $\varphi_3$ is satisfiable, then $\varphi_R$ is not satisfiable by itself, but can be made satisfiable by removing one of the introduced clauses, as the newly introduced literal $l$ can be set accordingly to make the remaining clause evaluate to true.

$\Leftarrow$: assume $\varphi_R$ has a clause at index $j$ that can be removed to make the remaining formula satisfiable.

Case 1: clause $C_j$ is in the original formula $\varphi_3$, then the two introduced clauses remain and the formula can't be satisfiable, leading to a contradiction.

Case 2: clause $C_j$ is one of the newly introduced clauses, then removing one of them leaves the original formula and a remaining clause that can trivially be assigned to evaluate to true.
The original formula must then also have been satisfiable.

\textbf{3-SAT} is NP-hard and by our reduction \textbf{RC3SAT} is also NP-hard.

\medskip


\begin{exercise}
	    An undirected graph is called a \emph{non-2-degree graph} if no vertex in the graph has exactly two edges to other vertices. \\ Examples:
        Graph $(\{a,b,c,d\},\{[a,b],[b,c],[b,d]\})$ is non-2-degree, while
          graphs $(\{a,b,c,d\},\{[a,b],[b,c],[c,d]\})$  or
        $(\{a,b,c\},\{[a,b],[b,c],[a,c]\})$  are not.
	 Consider the following decision problem:

\medskip

    \fbox{
      \begin{minipage}[c]{.9\linewidth}
	\textbf{3-COLORABILITY-N2D} 
	\smallskip

INSTANCE: A non-2-degree graph $G=(V,E)$.
\medskip

QUESTION: Does
          there exist a function $\mu$ from vertices in $V$ to values
          in $\{0,1,2\}$ such that $\mu(v_1)\neq \mu(v_2)$ for any
          edge $[v_1,v_2]\in E$.
      \end{minipage}
    }
	
\medskip


    Use the fact that the standard version of the \textbf{3-COLORABILITY} problem is NP-complete, to prove that
        \textbf{3-COLORABILITY-N2D}  is NP-complete as well.
Give a brief argument for NP-membership and show NP-hardness by a many-one reduction from
\textbf{3-COLORABILITY}.


\end{exercise}

\medskip

\noindent
\textbf{Solution:}

\textbf{3-COLORABILITY} instance: graph $G = (V, E)$

\textbf{3-COLORABILITY-N2D} instance: graph $G_{N2D} = (V_{N2D}, E_{N2D})$

We construct a valid \textbf{3-COLORABILITY-N2D} instance by introducing a new vertex $v_n$ for any vertices $v \in V$ for which there are exactly 2 edges $e_1, e_2 \in E$ and connecting this new vertex $v_n$ to $v$ with a new edge $e_n$.
The resulting graph $G_{N2D} = (V_{N2D}, E_{N2D})$ with the newly introduced vertices and edges becomes non-2-degree.
The reduction is $G = (V, E) \mapsto G_{N2D} = (V_{N2D}, E_{N2D})$.

$\Rightarrow$: assume $G$ is 3-colorable, then $G_{N2D}$ is also 3-colorable.
Any vertices $v_n \in V_{N2D} / V$ introduced by the reduction are connected by edge $e_n$ to a vertex $v \in V$ that was originally 2-degree.
Because the $G$ is 3-colorable, we only need to see whether there exists a valid coloring for the newly introduced vertices $v_n$.
Trivially they can be assigned any of the two remaining colors.

$\Leftarrow$: assume $G_{N2D}$ is 3-colorable.
Because $G$ is a strict subgraph of $G_{N2D}$, it follows that $G$ is also 3-colorable, because removing any vertices and edges does not change colorability.

\textbf{3-COLORABILITY-N2D} has the same certificates as \textbf{3-COLORABILITY} and is thus in NP.

\medskip


\begin{exercise}
  \label{ex:partition}

  	Consider the following decision problem:

\medskip     
   
    \fbox{
      \begin{minipage}[c]{.9\linewidth}
\textbf{INDEPENDENT DOMINATING SET (IDS)} 
	\smallskip

INSTANCE:  A directed graph $G=(V,E)$.
\medskip

QUESTION: 
 Does there exist a set $S\subseteq V$ of vertices, such that
        \begin{itemize}
        \item[(1)] for each $(u,v)\in E$, $\{u,v\}\not\subseteq S$;
        \item[(2)] for each $v\in V$ either $v\in S$ or there exists an edge $(u,v)\in E$, such that $u\in S$.
        \end{itemize}
      \end{minipage}
    }

\medskip
Show NP-hardness of \textbf{IDS} by providing a many-one reduction from
\textbf{3-SAT}.
  
\end{exercise}

\medskip

\noindent
\textbf{Solution:}

\textbf{3-SAT} instance: formula $\varphi$

\textbf{3-SAT} instance: graph $G = (V, E)$

We construct a graph $G = (V, E)$ with the following properties:

For every literal, we add both the positive and negative forms $x_i$ and its dual counterpart $x_i^d = \neg x_i$ and edges $(x_i, x_i^d), (x_i^d, x_i)$.
For every clause we add a vertex $c_i$.
Assuming without loss of generality that clause $c_j$ has literals $x_1, x_2, x_3$, we add edges $(x_1, c_j), (x_2, c_j), (x_3, c_j), (c_j, c_j)$.

This results in a graph in which we cannot choose vertices $c_j$ because of their self-edges.
It remains to choose either $x_i$ or $x_i^d$ but not both, because they are implicitly connected.
We have to choose all $x_i$ or $x_i^d$ to cover all $c_j$, which creates a direct correspondence to satisfiability of all clauses.
A chosen vertex corresponds to setting that literal to true but not its dual counterpart.

$\Rightarrow$: we assume $\varphi$ is satisfiable.
This means every clause $c_j$ must have at least one literal $x_j$ that evaluates to true.
We can choose literal $x_j$ as a vertex in our independent dominating set.
Thus vertex $x_j$ is contained (and $x_j^d$ is not) and it covers $c_j$, $x_j$ and $x_j^d$.
This shows that all clause vertices $c_j$ are covered.
Because a valid truth assignment must assign all variables, automatically we have that all literals are covered (either by $x_i$ or $x_i^d$)
Because the graph consists only of vertices $c_j$ and $x_i$ we have an independent dominating set.

$\Leftarrow$: we assume that we have an independent set of vertices $S \subset V$.
Vertices $s \in S$ can not be one of the clause vertices $c_j$, because they have self-edges.
Thus, $S$ can consist only of literal vertices $x_i$ and $x_i^d$.
Because $x_i$ and $x_i^d$ are bi-directionally connected, only either one can be in $S$, corresponding to a valid truth assignment.
Because vertices $S$ cover all vertices, all clause vertices $c_j$ and literal vertices $x_i$ and $x_i^d$ are covered.
If vertex $x_i$ is in $S$, then variable $i$ is set to true.
If instead vertex $x_i^d$ is in $S$, then variable $i$ is set to false.
As every clause vertex is covered by either $x_i$ or $x_i^d$, every corresponding clause in $\varphi$ must contain a literal that evaluates to true, thus making $\varphi$ satisfiable.

By way of our reduction, our knowledge of the NP-hardness of \textbf{3-SAT} implies the NP-hardness of \textbf{INDEPENDENT DOMINATING SET}.

\medskip


\begin{exercise}
	Provide a polynomial-time many-one reduction from \textbf{2-COLORABILITY} to \textbf{2-SAT}. 
	Given that \textbf{2-SAT} is in $P$, what can be said about the complexity of \textbf{2-COLORABILITY}?
\end{exercise}

\medskip

\noindent
\textbf{Solution:}

\textbf{2-COLORABILITY} instance: graph $G = (V, E)$

\textbf{2-SAT} instance: formula $\varphi$

We construct a formula $\varphi$ by looking at each edge $e_i$.
For each edge $e_i = (v_1, v_2)$ we introduce to clauses $(x_1 \lor \neg x_2) \land (\neg x_1 \lor x_2)$.
This conjunction of clauses corresponds to an exclusive or between variables $x_1$ and $x_2$.
We simply connect all resulting clause pairs conjunctively.

$\Rightarrow$: assume $G$ is 2-colorable with colors $c \in {t, f}$.
For each vertex $v_i$, we can set the value of the variable $x_i$ to true if its color if $t$ (and false otherwise).
Because no two neighboring nodes $v_i$ and $v_j$ are set to the same color, every clause pair $(x_i \lor \neg x_j) \land (\neg x_i \lor x_j)$ has either $v_i$ or $v_j$ colored with $t$ and thus either $x_i$ or $x_j$ set to true, but not both and thus the clause pair evaluates to true.
Because this is true of any two connected vertices (of any edge), the whole formula $\varphi$ must evaluate to true and is satisfiable.

$\Leftarrow$: assume $\varphi$ is satisfiable.
Coloring function $\mu(i)$ assigns color $t$ to $v_i$ if and only if variable $x_i$ is set to true (and color $f$ otherwise).
We can show that $G$ is 2-colorable by way of contradiction:
assume there exists an edge $e = (v_i, v_j)$ that have the same color.
This means that their corresponding variables $x_i$ and $x_j$ are set to the same truth value, $x_i = x_j$.
There must be a clause pair $(x_i \lor \neg x_j) \land (\neg x_i \lor x_j)$ that evaluates to true according to our original assumption of the satisfiability of $\varphi$.
This is a contradiction, because $x_i$ and $x_j$ can only exclusively be set to true.
Therefore our assumption that $v_i$ and $v_j$ have the same color must be wrong and as such, no two adjacent vertices are assigned the same color, making the graph 2-colorable.

\end{document}


